Définition équivalente d'une congruence

Propriété  Définition équivalente à celle donnée précédemment

Soit $a,b\in \mathbb{Z}$ et $n\in {\mathbb{N}}^{\ast }$ . On a 
$a\equiv b[n]⟺a$  et $b$  ont le même reste dans la division euclidienne par $n$ .

 Exemples  Congruences modulo 7

• On a : $30=4\times 7+2$ et $44=6\times 7+2$ qui correspondent à des divisions euclidiennes par $7$ avec le même reste $2$ . Par conséquent : $30\equiv 44[7]$ .
  
• Comme $23=3\times 7+2$ , on a aussi $23\equiv 30[7]$ et $23\equiv 44[7]$ .
  

Démonstration

On écrit les divisions euclidiennes de $a$ et $b$ par $n$ :
$a=nq+r$ avec \(0 \leqslant r 
et  $b=n{q}^{\prime }+r^{\prime }$ avec  \(0 \leqslant r'.
En soustrayant les deux égalités, on obtient :
$a-b=nq+r-n{q}^{\prime }-r^{\prime }=n(q-q^{\prime })+(r-r^{\prime })$
De plus,  $0⩽r^{\prime }<n⟺-n<-r^{\prime }⩽0$ .
Comme  \(0 \leqslant r et  $-n<-r^{\prime }⩽0$ , on obtient, en ajoutant ces inégalités,  \(-n.

Montrons l'équivalence souhaitée par double implication.

$[\Rightarrow ]$ Supposons que $a\equiv b[n]$ . Montrons que $r=r^{\prime }$ .
Alors $a-b$ est un multiple de $n$ , donc il existe $k\in \mathbb{Z}$ tel que $a-b=kn$ .
On a donc :
$\begin{array}{rl}a-b=n(q-q^{\prime })+(r-r^{\prime })& ⟺kn=n(q-q^{\prime })+(r-r^{\prime })\\ & ⟺r-r^{\prime }=kn-n(q-q^{\prime })\\ & ⟺r-r^{\prime }=n(k-q+q^{\prime })\end{array}$
donc $r-r^{\prime }$ est un multiple de $n$ .
Comme  \(-n, on a nécessairement  $r-r^{\prime }=0$  et donc  $r=r^{\prime }$ .

$[\Leftarrow ]$ Supposons que $r=r^{\prime }$ .
On a alors $a-b=n(q-q^{\prime })$ , donc $a-b$ est un multiple de $n$ , donc $a\equiv b[n]$ .